package mo.offer_special;

import mo.leetcode_top.L11;

public class L116 {


    public int findCircleNum(int[][] isConnected) {
        int ret = 0;
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, i, n);
                ret++;
            }
        }
        return ret;
    }

    private void dfs(int[][] isConnected, boolean[] visited, int i, int n) {
        visited[i] = true;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && isConnected[i][j] == 1) {
                dfs(isConnected, visited, j, n);
            }
        }
    }

    public static void main(String[] args) {
        L116 test = new L116();
        System.out.println(test.findCircleNum(new int[][]{
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1}
        }));
    }
}
